package airthmetic.exercise.stack;

import java.util.ArrayDeque;
import java.util.Deque;

public class _42_接雨水 {

    public static int trap(int[] height) {
        // 特殊判断
        if (height == null) {
            return 0;
        }
        // 构造单调栈,此处两边不需要哨兵,原因是因为两侧肯定是装不了水的,如果加入了哨兵要么就让两侧能装水了,要么就是导致中间的计算结果不正确
        Deque<Integer> stack = new ArrayDeque();
        // 定义最大值
        int max = 0;
        // 数组元素依次入栈
        for (int i=0;i<height.length;i++) {
            while (!stack.isEmpty() && height[i] >= height[stack.peek()]) {
                int p = stack.pop();
                if (!stack.isEmpty()) {
                    max += (Math.min(height[stack.peek()], height[i]) - height[p]) * (i - stack.peek()-1);
                }
            }
            stack.push(i);
        }
        return max;
    }


    public static void main(String[] args) {
        int[] height = new int[]{8,3,4};
        System.out.println(trap(height));
    }
}
